FIELD OF THE INVENTION
The present invention relates to an interference checking method for two non-convex polyhedrons and, more particularly, to an interference checking method for judging whether the CG models of objects constructed in a computer are spaced apart from or in contact with one another by the computer, and calculating the points of closest approach, the point of contact and the distance between the points of closest approach in real time. The present invention is applicable to various fields to which computer graphics is applied such as CAD systems for designing a mechanism, path generation for manipulators and mobile robots such as self-propelled vehicles, creation of animations for multimedia use and game software.
When a plurality of CG models (CG model is a set of polygons for determining the shape of an object) are constructed in a graphic computer, it is desired to judge whether the CG models having arbitrary convex and concave parts are spaced apart from or in contact with one another and to calculate the points of closest approach in the former case and the point of contact in the latter case in real time. Not only in the case of CG models in a graphic computer but also when mathematical models (each consisting of vertexes in three-dimensional coordinates, a set of edges and a set of faces) of objects are given, search for the points of closest approach/point of contact of the mathematical models is generally called "search for the points of closest approach".
The basic method used to search for the points of closest approach is to enter data representing the shape, position and attitude of a particular object in a computer and solving the problem by elementary geometrical calculations. A graphic simulator used in the field of CAD usually expresses a single object by pasting together a plurality of planar convex polygons. Accordingly, the simplest method of checking the state of interference between two objects is therefore a method of checking the interference between a pair of polygons which constitute the respective objects with respect to all kinds of combinations. More specifically, in a pair of polygons disposed arbitrarily in a space, the points of closest approach are searched for with respect to each lattice point, side and face, and the distance between the points of closest approach is calculated. It goes without saying that if the distance between the points of closest approach is zero, two polygons are in the state of interference. Since this method is accompanied by a large computation load of O(M.sub.1 .multidot.M.sub.2), wherein M.sub.1, M.sub.2 represent the number of lattice points expressing the two objects, it lacks in real-timeness.
Historically, methods of searching for the points of closest approach include a method using a Voronoi diagram illustrating the proximity relationship of each lattice point by connecting the perpendicular bisectors between lattice points, as well as the oct-tree method in which three-dimensional space is successively divided into eight equal portions quadrant by quadrant and the exclusive area of the object is made a data base. Both of these methods are useful in cases where an object is fixed statically, but they are unsuitable when the object of interference check successively changes dynamically due to disassembly or assembly.
In the field of robotics, the Boblow method, the Lin/Canny method and the Gilbert method are known as a high-speed interference checking algorithm, and any of these methods enables the points of closest approach to be calculated in a space of time of not more than O(N) (N: the total number of lattice points of the object of interference check). However, the objects of inspection to which these methods are applicable are limited to convex polyhedrons.
Most of the shapes which can be designed by using a commercially available three-dimensional CAD system such as Pro/Engineer are non-convex polyhedrons, so that a method having real-timeness such as the Boblow method, the Lin/Canny method and the Gilbert method is not adopted when the interference between parts with non-convex polyhedrons is checked, and a method of respectively checking the interference between each pair of polygons which constitute the respective parts of a shape or a method of analytically and gradually solving the equation which defines a shape is adopted.
As an interference checking method for non-convex polyhedrons, the Quinlan method is known. This is a method of covering a polyhedron with a set of spheres which are hierarchically arranged, checking the interference between each pair of spheres so as to obtain a pair of polygons which are approaching closest, and then adopting the Gilbert method. Although this method is a very general method which is applicable to an arbitrary non-convex polyhedron, it is defective in that when the strict distance between two objects is computed, the number of spaces to be searched increases, so that the computation time is greatly prolonged.
In addition, such a conventional interference checking method is disadvantageous in that it is impossible in real-time to judge whether non-convex polyhedrons are spaced apart from or in contact with one another, and to calculate the points of closest approach in the former case and the point of contact in the latter case.